package com.algorithm.cjm.csnote

import java.util.*

/**
 * 排序，基于《算法》第四版
 *
 * Created by jieming.chen on 2021/2/12
 */

// 交换
fun exch(a: IntArray, v: Int, w: Int) {
    val temp = a[v]
    a[v] = a[w]
    a[w] = temp
}
// 比较, 小于
fun less(v: Int, w: Int): Boolean {
    return v < w
}
// 比较, 小于等于
fun lessAndEqual(v: Int, w: Int): Boolean {
    return v <= w
}

// 是否有序
fun isSorted(a: IntArray): Boolean {
    for (i in  1 until a.size) {
        if (less(a[i], a[i - 1])) {
            return false
        }
    }
    return true
}

/**
 * 选择排序
 * 从小到大 升序排列
 */
fun selectionSort(a: IntArray) {
    for (i in a.indices) {
        var min = i
        for (j in (i + 1) until a.size) {
            if (less(a[j], a[min])) {
                min = j
            }
        }
        exch(a, min, i)
    }
}

/**
 * 插入排序
 * 从小到大，升序排序
 */
fun insertionSort(a: IntArray) {
    for (i in 1 until a.size) {
        for (j in i downTo 1) {
            if (less(a[j], a[j - 1])) {
                exch(a, j, j - 1)
            }
        }
    }
}

/**
 * 希尔排序
 * 对插入排序的改良
 * 从小到大，升序排列
 *
 * 1. 用公式求出分成数列的系数
 * 2. 分成 h个 子数列
 * 3. 分别对 子数列进行插入排序
 * 4. 当子数列的步长为1时，再进行插入排序
 */
fun shellSort(a: IntArray) {
    val n = a.size
    var h = 0
    while (h < n/3) h = h * 3 + 1 // 1, 4, 13, 40

    while (h > 0) {
        for (i in h until n) {
            for (j in i downTo 0 step h) {
                if (j - h >= 0 && less(a[j], a[j -h])) {
                    exch(a, j, j -h)
                }
            }
        }
        h /= 3
    }
}


private var aux: IntArray = IntArray(100)

/**
 * 原地归并
 * 把两个有序数组合并成为一个大数组
 */
fun merge(a: IntArray, start: Int, mid: Int, end: Int) {
    // 把数组a 的元素复制到数组 aux
    for (i in start .. end) {
        aux[i] = a[i]
    }
    var p0 = start
    var p1 = mid + 1
    var index = start
    while (index <= end) {
        // 左部分已经比较复制完成了，把右部分还没有赋值完成的直接赋值
        if (p0 > mid) {
            a[index++] = aux[p1++]
        } else if (p1 > end) {
            // 右部分已经比较复制完成了，把左部分还没有赋值完成的直接赋值
            a[index++] = aux[p0++]
        } else if (less(aux[p0], aux[p1])) {
            a[index++] = aux[p0++]
        } else {
            a[index++] = aux[p1++]
        }
    }
}

/**
 * 归并排序, 利用递归
 * 自顶向下
 */
fun guiBinSortTopToDown(a: IntArray) {
    aux = IntArray(a.size)
    guiBinSort1(a, 0, a.size - 1)
}
fun guiBinSort1(a: IntArray, start: Int, end: Int) {
    if (start >= end) {
        return
    }
    val mid = (start + end) / 2
    guiBinSort1(a, start, mid)
    guiBinSort1(a, mid + 1, end)
    merge(a, start, mid, end)
}

/**
 * 归并排序
 * 自底向上，
 * 会多次遍历整个数组，根据子数组的大小进行两两归并，
 * 子数组的大小 sz 的初始值为1，每次加倍。
 * 最后一个子数组的大小只有在数组大小是 sz 的
 * 偶数倍的时候才会等于sz(否则它会比sz 小)
 *
 */
fun guiBinSortDownToTop(a: IntArray) {
    val N = a.size
    aux = IntArray(N)
    var sz = 1
    while (sz < N) {
        var lo = 0
        while (lo < N - sz) {
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1))
            lo += sz + sz
        }
        sz = sz + sz
    }
}

/**
 * 快速排序
 * 双边循环
 */
fun quickSort(a: IntArray) {
    quickSort(a, 0, a.size -1)
}

fun quickSort(a: IntArray, start: Int, end: Int) {
    if (start >= end) {
        return
    }

    val partitionIndex = partitionForQuickSort1(a, start, end)
    quickSort(a, start, partitionIndex -1)
    quickSort(a, partitionIndex + 1, end)
}

/**
 * 划分
 */
fun partitionForQuickSort(a: IntArray, start: Int, end: Int): Int {
    var p0 = start
    var p1 = end

    // 基准点，也可以先打乱数组然后再取第一个元素
    val m = a[p0]

    while (p0 < p1) {
        while (p1 > p0 && lessAndEqual(m, a[p1])) {
            p1--
        }
        while (p0 < p1 && lessAndEqual(a[p0], m)) {
            p0++
        }
        if (p0 < p1) {
            exch(a, p1, p0)
        }
    }
    exch(a, start, p0)
    return p0
}

fun partitionForQuickSort1(a: IntArray, start: Int, end: Int): Int {
    var i = start
    var j = end + 1
    val m = a[start]

    while (true) {
        while (less(m, a[--j])) {
            if (j == start) break
        }
        while (less(a[++i], m)) {
            if (i == end) break
        }
        if (i >= j) {
            break
        }
        exch(a, i, j)
    }
    exch(a, start, j)
    return j
}

/**
 * 快速排序
 * 单边循环
 */
fun quickSort2(a: IntArray) {
    quickSort2(a, 0, a.size -1)
}

fun quickSort2(a: IntArray, start: Int, end: Int) {
    if (start >= end) {
        return
    }

    val partitionIndex = partitionForQuickSort2(a, start, end)
    quickSort2(a, start, partitionIndex - 1)
    quickSort2(a, partitionIndex + 1, end)
}

fun partitionForQuickSort2(a: IntArray, start: Int, end: Int): Int {
    val m = a[start]
    var p0 = start

    for (i in start.. end) {
        if (lessAndEqual(a[i], m)) {
            exch(a, i, p0++)
        }
    }
    exch(a, start, p0 - 1)
    return p0 - 1
}

fun quickSort3(a: IntArray) {
    quickSort3(a, 0, a.size -1)
}

fun quickSort3(a: IntArray, start: Int, end: Int) {
    val quickSortStack = Stack<Map<String, Int>>()
    val rootParam = mapOf<String, Int>("startIndex" to start, "endIndex" to end)
    quickSortStack.push(rootParam)

    while (quickSortStack.isNotEmpty()) {
        val pop = quickSortStack.pop()
        val i = pop["startIndex"]!!
        val j = pop["endIndex"]!!
        val partitionIndex = partitionForQuickSort3(a, i, j)

        if (partitionIndex -1 > i) {
            val leftParam = mapOf<String, Int>("startIndex" to i, "endIndex" to partitionIndex - 1)
            quickSortStack.push(leftParam)
        }
        if (j > partitionIndex + 1) {
            val rightParam = mapOf<String, Int>("startIndex" to partitionIndex + 1, "endIndex" to j)
            quickSortStack.push(rightParam)
        }
    }
}

fun partitionForQuickSort3(a: IntArray, start: Int, end: Int): Int {
    val m = a[start]
    var p0 = start

    for (i in start.. end) {
        if (lessAndEqual(a[i], m)) {
            exch(a, i, p0++)
        }
    }
    exch(a, start, p0 - 1)
    return p0 - 1
}

fun main(args: Array<String>) {
//    // 测试选择排序
//    val intArrayOf = intArrayOf(5, 3, 2, 7, 8, 19)
//    selectionSort(intArrayOf)
//    assert(isSorted(intArrayOf))
//
//    // 测试插入排序
//    val intArrayOf1 = intArrayOf(5, 3, 2, 7, 8, 19)
//    insertionSort(intArrayOf1)
//    println(intArrayOf1.contentToString())
//    assert(isSorted(intArrayOf1))
//
//    // 测试希尔排序
//    val intArrayOf2 = intArrayOf(5, 3, 2, 7, 8, 19)
//    shellSort(intArrayOf2)
//    println(intArrayOf2.contentToString())
//
//
//    // 测试merge操作
//    val intArrayOf3 = intArrayOf(5, 6, 11, 2, 3, 10)
//    merge(intArrayOf3, 0, 2, 5)
//    println(intArrayOf3.contentToString())
//
//    // 测试归并排序
//    val intArrayOf4 = intArrayOf(5, 6, 11, 7, 2, 3, 10, 11)
//    guiBinSortTopToDown(intArrayOf4)
//    println(intArrayOf4.contentToString())

    // 测试快速排序, 双边
    val intArrayOf5 = intArrayOf(5, 6, 11, 7, 2, 3, 10, 11)
    quickSort(intArrayOf5)
    println(intArrayOf5.contentToString())

    // 测试快速排序, 单边
//    val intArrayOf6 = intArrayOf(5, 6, 11, 7, 2, 3, 10, 11)
//    quickSort2(intArrayOf6)
//    println(intArrayOf6.contentToString())
//
//    // 用栈来实现快速排序
//    val intArrayOf7 = intArrayOf(5, 6, 11, 7, 2, 3, 10, 11)
//    quickSort3(intArrayOf7)
//    println(intArrayOf7.contentToString())
}